package leetcode.array;

import leetcode.Hot100.subarraySum;

import java.util.HashMap;

/**
 * @author Cheng Jun
 * Description: 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度
 * https://leetcode.cn/problems/contiguous-array/
 * 1 <= nums.length <= 10^5
 * nums[i] 不是 0 就是 1
 * @version 1.0
 * @date 2022/7/17 9:52
 * @see subarraySum
 */
public class findMaxLength {
    public static void main(String[] args) {
        int[] nums = {0,1,0,1,1,0};
        System.out.println(findMaxLength(nums));
    }


    // 前缀和，
    static int findMaxLength(int[] nums) {
        // 0, 1
        // 0, 0, 0,  1, 0, 0, 0, 0, 1 1
        // -1 -2 -3 -2 -3 -4 -5 -6 -5 -4
        // 思路把 0 看做 -1 最长连续子数组
        int res = 0;
        int preSum = 0;
        HashMap<Integer, Integer> preMap = new HashMap<>();
        // 注意：一定要提前把 preSum 存进去， value为-1的特性不好解释，用来被数组下标减的
        preMap.put(preSum, -1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) preSum += -1;
            else preSum += 1;
            if (preMap.get(preSum) == null) {
                    preMap.put(preSum, i);
            } else {
                int index = preMap.get(preSum);
                res = Math.max(res, i - index);
            }
        }
        return res;
    }

    // 时间复杂度 O(n^2)，提交Leetcode 超时
    @Deprecated
    static int findMaxLength1(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 0) sum += -1;
                else sum += 1;
                if (sum == 0) res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}
